package com.liyghting.datastructurealgorithm.sort;

/**
 * 基于数组实现冒泡，插入，选择排序，时间复杂度都为O(n*n)
 * 
 * @author LiYiGuang
 * @date 2018/11/23 15:46
 */
public class ArraySort {
	// 冒泡排序
	public static void bubbleSort(int[] a, int n) {
		if (n <= 1)
			return;
		for (int i = 0; i < n; i++) {
			// 提前退出冒泡循环的标志位
			boolean flag = false;
			for (int j = 0; j < n - i - 1; j++) {
				if (a[j] > a[j + 1]) {// 交换
					int temp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = temp;
					flag = true;
				}
			}
			if (!flag)
				break;
		}
	}

	// 插入排序
	public static void insertionSort(int[] a, int n) {
		if (n <= 1)
			return;
		for (int i = 1; i < n; i++) {
			int value = a[i];
			int j = i - 1;
			// 查找插入数据
			for (; j >= 0; j--) {
				if (a[j] > value) {
					a[j + 1] = a[j];// 数据移动
				} else {
					break;
				}
			}
			a[j + 1] = value; // 插入数据
		}
	}

	// 选择排序
	public static void selectionSort(int[] a, int n) {
		if (n <= 1)
			return;
		for (int i = 0; i < n - 1; i++) {
			// 查找最小值
			int minIndex = i;
			for (int j = i + 1; j < n; j++) {
				if (a[j] < a[minIndex]) {
					minIndex = j;
				}
			}
			// 交换
			int temp = a[i];
			a[i] = a[minIndex];
			a[minIndex] = temp;
		}
	}

	public static void print(int[] a, int n) {
		for (int i = 0; i < n; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int[] a = { 4, 5, 6, 3, 2, 1 };
		bubbleSort(a, 6);
		print(a, 6);
		int[] b = { 4, 5, 6, 3, 2, 1 };
		insertionSort(b, 6);
		print(b, 6);
		int[] c = { 4, 5, 6, 3, 2, 1 };
		selectionSort(c, 6);
		print(c, 6);
	}
}
